package javabase.schoolwork.day6_4;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author fance
 * @date 18-6-4 下午12:42
 */
public class StringSum {
    /**
     * 最长公共字串
     * @param s1
     * @param s2
     * @return
     */
    public String maxCommonSub(String s1, String s2) {
        if (s1 == null || s1.length() < 1 || s2 == null || s2.length() < 1) {
            return null;
        }
        String res = null;
        int maxLen = 0;
        // 假定 s2 更短
        for (int i = 0; i < s2.length() - 1; i++) {
            for (int j = i + 1; j <= s2.length(); j++) {
                String cur = s2.substring(i,j);
                if (s1.contains(cur) && cur.length() > maxLen) {
                    maxLen = cur.length();
                    res = cur;
                }
            }
        }
        return res;
    }

   /* *//**
     * 最长公共字串
     * @param s1
     * @param s2
     * @return
     *//*
    public String lcst(String s1,String s2) {
        if (s1 == null || s1.length() < 1 || s2 == null || s2.length() < 1) {
            return null;
        }
        char[] cs1 = s1.toCharArray();
        char[] cs2 = s2.toCharArray();
        int[][] dp = getDpForLcst(cs1,cs2);
        int end = 0;
        int max = 0;
        for (int i = 0; i < cs1.length; i++) {
            for (int j = 0; j < cs2.length; j++) {
                if (dp[i][j] > max) {
                    end = i;
                    max = dp[i][j];
                }
            }
        }
        return s1.substring(end - max + 1,end + 1);
    }

    private int[][] getDpForLcst(char[] str1,char[] str2) {
        int[][] dp = new int[str1.length][str2.length];
        for (int i = 0; i < str1.length; i++) {
            if (str1[i] == str2[0]) {
                dp[i][0] = 1;
            }
        }
        for (int i = 0; i < str2.length; i++) {
            if (str1[0] == str2[i]) {
                dp[0][i] = 1;
            }
        }

        for (int i = 1; i < str1.length; i++) {
            for (int j = 1; j < str2.length; j++) {
                if (str1[i] == str2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
            }
        }
        return dp;
    }
*/

    public String sort(String s) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        return String.valueOf(chars);
    }

    @Test
    public void test() {
        /*String s1 = "abcdefgh";
        String s2 = "xtsadeffasdfasd";
        long st = System.currentTimeMillis();
        System.out.println(maxCommonSub(s1,s2));
        System.out.println(System.currentTimeMillis() - st);

        long st2 = System.currentTimeMillis();
        //System.out.println(lcst(s1,s2));
        System.out.println(System.currentTimeMillis() - st2);
    */}
}
